<HTML>
<HEAD>
<TITLE>Paxi Language Definition</TITLE>
</HEAD>

<font size = 4>
<body bgcolor = "ffffff">

<CENTER><H1>Paxi Language Definition</H1>
<img src="paxi_small.jpg" width="200">
<H3>David Nordstrom
<BR>George Mason University</H3>
</CENTER>

<P><H3>The Language</H3>

Paxi is a simple programming language intended for a compiler writing
project at George Mason University.  It supplies minimal but
representative programming facilities and is designed for ease of
implementation.

<P>The canonical "Hello, world!" program looks like this in Paxi:

<BLOCKQUOTE><PRE>
proc main()
     writestr("Hello, world!");  line;
endproc
</PRE></BLOCKQUOTE>

<P><H3>Program Structure</H3>

A Paxi program consists of a declaration section, in which global
variables are declared, and a code section.  The code section is a
list of <EM>procedures</EM>.  Procedures accept parameters, have local
variables and can optionally return a result.  The entry point to a
Paxi program is always a procedure called <EM>main</EM>. Paxi is case
sensitive.  All text between <STRONG>//</STRONG> and
the end of the line is a comment.

<P><H3>Data</H3>

<P>Variables are declared with the keywords <STRONG>var</STRONG>, for
scalar variables, and <STRONG>array</STRONG> for arrays.  All
variables are integers.  Below "[[item]]" means a comma-separated list
of <EM>one or more</EM> items.  A <EM>declaration</EM> has the form

<BLOCKQUOTE><PRE>
var [[identifier]];
</PRE></BLOCKQUOTE>
<P>for scalar variables or
<BLOCKQUOTE><PRE>
array [[number indentifier]];
</PRE></BLOCKQUOTE>
<P>for arrays.  Any number of declarations can appear in the
declaration section.

<P>An <EM>identifier</EM> is any string of letters, digits, and
underscores beginning with a letter or underscore.  A Paxi compiler
must accept identifiers up to 20 characters long (but may accept
longer).  <EM>Number literals</EM> in Paxi are decimal integers.

<P>The <EM>number</EM> above is the dimension of the array.  Array
indexing is zero-based and any arithmetic expression can be used as an
array index.  An array index is encloses in brackets.

<P><EM>Character strings</EM> are stored in integer arrays (since
integer is the only type available to us in Paxi).  Strings are stored
as ASCII codes with a 0 terminator.  Single <EM>characters</EM> are
enclosed in single quote marks (e.g. 'A').  A character may be used
where ever a number is expected and is treated as an ASCII code.

<P><H3>Procedures</H3>

Paxi subprograms are called procedures.  They are introduced by the
keyword <STRONG>proc</STRONG> followed by the procedure name (an
identifier) and a (possibly empty) comma-separated parameter list
enclosed in parentheses.  They end with the keyword
<STRONG>endproc</STRONG>.  The formal parameters are identifiers and
are treated as (scalar) local variables within the procedure.
Procedures cannot contain other procedures.

<P>Following the procedure name and parameters comes a (possibly
empty) list of local variable declarations.  Local variables
<EM>cannot</EM> be arrays but are otherwise declared just like global
variables.  The scope of a local variable is the procedure which
contains it.  The local declarations are followed by a <EM>statement
list</EM>.  Statements are terminated by semi-colons.  The following
is a simple example procedure:


<BLOCKQUOTE><PRE>
proc haha(i, j)
var temp;  // all local declarations precede the statement list
   writestr("The first parameter has value ");
   write(i); line;
   temp = 3*j;
   writestr("Three times the second is ");
   write(temp); line;
endproc
</PRE></BLOCKQUOTE>

<P>Procedures are called in the usual way, with any (integer-valued)
arithmetic expressions for parameters:

<BLOCKQUOTE><PRE>
// calling haha:
   haha(7, a[x + 9]*4);
</PRE></BLOCKQUOTE>

<P>Procedures may return a value.  The <STRONG>retval</STRONG>
statement saves a value to be used as a return value.  When the
procedure is called its value is the <EM>last</EM> value saved this
way in the procedure.

<BLOCKQUOTE><PRE>
proc sum(i, j)
   retval i + j;
endproc

proc main()
var in1;
var in2;
   writestr("->  ");  read(in1);
   writestr("->  ");  read(in2);
   writestr("Sum is ");
   write(sum(in1, in2)); line;
endproc
</PRE></BLOCKQUOTE>

<P><STRONG>retval</STRONG> does <EM>not</EM> cause a return from a
procedure -- it only associates a value.  If a procedure containing a
<STRONG>retval</STRONG> statement does not appear inside an
expression where a value is expected the return value is ignored.
If a procedure is used where a value is expected but it does not
contain a <STRONG>retval</STRONG> statement its value is undefined.

<P>Forward references are not allowed (a procedure can only call
procedures which precede it in the program) but a procedure can call
itself recursively.

<P><H3>Input and Output</H3>

Paxi has very limited input and output, and no file I/O.

<P>Integer values are read with the <STRONG>read</STRONG> statement
and written with the <STRONG>write</STRONG> statement.

<BLOCKQUOTE><PRE>
// accept a value into variable i
   read(i);
// display an integer value:
   write(i + 2);
</PRE></BLOCKQUOTE>

<P>Strings are read and written with <STRONG>readstr</STRONG> and
<STRONG>writestr</STRONG>.

<P><STRONG>writestr</STRONG> can take either a string literal (in
double quotes) or an array name as an argument.  If
<STRONG>writestr</STRONG> takes an array name it displays a character
for each element in the array up to (not including) the first 0 in the
array treating each character as an ASCII code.

<P><STRONG>readstr</STRONG> takes an array name as argument.  Input is
stored in the array as ASCII codes, one character to an (integer)
array element, with a terminating 0.  It is the programmer's
responsibility to see that the array is large enough to hold the input
string and terminating 0.  All input is accepted from the keyboard up
to the newline (when the user hits the enter key).  The newline
character is not stored with the string.

<P>When the following is run

<BLOCKQUOTE><PRE>
array 80 instring;

proc main()
   writestr("What is your name?  ");
   readstr(instring);
   writestr("Well hello, ");
   writestr(instring);
   writestr("!"); line;
endproc
</PRE></BLOCKQUOTE>

<P>the output may look like:

<BLOCKQUOTE><PRE>
What is your name?  Johann Sebastian Bach
Well hello, Johann Sebastian Bach!
</PRE></BLOCKQUOTE>

<P>All characters inside a string are displayed literally, there are
no "escaped" characters.  A newline is displayed by using the
<STRONG>line</STRONG> statement.

<P><H3>Arithmetic</H3>

All arithmetic is integer arithmetic.  Arithmetic expressions use the
usual operators: <STRONG>+</STRONG>, <STRONG>-</STRONG>,
<STRONG>*</STRONG>, and <STRONG>/</STRONG>.  They have the usual
precedence and parentheses have the expected meaning.  When a
procedure returns a value the procedure call can appear where an
integer value is to be used.


<P><H3>Boolean Expressions</H3>

The simplest boolean expressions have the form <EM>(arithmetic_expression
relational_operator arithmetic_expression)</EM>, for example:

<BLOCKQUOTE><PRE>
(a < b)
(var1 = 0)
(3*x[5] <= y)
</PRE></BLOCKQUOTE>

<P>The relational operators are <STRONG>&lt;</STRONG>,
<STRONG>&lt;=</STRONG>, <STRONG>&gt;=</STRONG>, <STRONG>&gt;</STRONG>,
<STRONG>=</STRONG>, and <STRONG>#</STRONG>.  "<STRONG>=</STRONG>" tests
equality and "<STRONG>#</STRONG>" tests for "not equal to."
"<STRONG>=</STRONG>" is used both as test for equality and for the
assignment operator.

<P>These simple expressions can then be combined with binary operators
<STRONG>and</STRONG> and <STRONG>or</STRONG> and the unary operator
<STRONG>not</STRONG>.  <STRONG>not</STRONG> has higher precedence than
<STRONG>and</STRONG> and <STRONG>and</STRONG> has higher precedence
than <STRONG>or</STRONG>.  Parentheses can be used to make
sub-expressions be evaluated before other operators are applied.  It
is not necessary to have a pair of parentheses enclosing the entire
expression.

<P>Example Boolean expressions:

<BLOCKQUOTE><PRE>
(a < b) and (b > 0) or (b < a) and (a > 0)

not((nextval() = 0) or (nextval() = -1))
</PRE></BLOCKQUOTE>

<P><H3>Control Structures</H3>

<P>There are three control structures in Paxi: <EM>if</EM> (with
optional <EM>else</EM>), <EM>while</EM> loop, and <EM>do while</EM> loop.  All
control structures may be nested.

<P>Example if statements:

<BLOCKQUOTE><PRE>
if (var1 <= var2) and not (var1 = 0)
   write(var2/var1);
   var1 = var1 + 1;
endif;

if (i < 0)
   writestr("negative"); line;
else
   writestr("non-negative"); line;
endif;
</PRE></BLOCKQUOTE>

<P>The <EM>if</EM> statement is ended with the keyword
<STRONG>endif</STRONG>.  The <EM>list</EM> of statements between
<STRONG>if</STRONG> and <STRONG>endif</STRONG>, or between
<STRONG>if</STRONG> and <STRONG>else</STRONG> and then between
<STRONG>else</STRONG> and <STRONG>endif</STRONG> are controlled as
blocks.

<P>The <EM>while</EM> and <EM>do while</EM> loops also control
statement lists.  <EM>while</EM> loops end with
<STRONG>endwhile</STRONG> and the statement list controlled in a
<EM>do while</EM> loop ends with <STRONG>endo</STRONG>.  Examples:

<BLOCKQUOTE><PRE>
while (guess # target)
   writestr("Guess again  ");
   read(guess);
endwhile;

do
   writestr("Enter y or n:  ");
   readstr(instring);
endo
while (instring[0] # 'y') and (instring[0] # 'n');
</PRE></BLOCKQUOTE>

<P><H3>A Program</H3>

Finally, a complete (though not very interesting) program:

<BLOCKQUOTE><PRE>
// all global declarations up here
array 80 instr;

// now write procedures
proc is_letter(ch)
// this procedure can be called as a function
   if (ch >= 'a') and (ch <= 'z') or
               (ch >= 'A') and (ch <= 'Z')
      retval 1;
   else
      retval 0;
   endif;
endproc
   
proc main()
var i, letter_count;  // local declaration
   writestr("Type something:  ");
   readstr(instr);
   letter_count = 0;
   i = 0;
   while (i < 80) and (instr[i] # 0)
      if (is_letter(instr[i]) = 1)
         letter_count = letter_count + 1;
      endif;
      i = i + 1;
   endwhile;
   writestr(instr); writestr (" has ");
   write(letter_count); writestr(" letters"); line;
endproc
</PRE></BLOCKQUOTE>

<P><H3>Keywords and Symbols</H3>

<EM>Keywords</EM> are reserved, i.e. they may not be used as
identifiers.  The reserved words in Paxi are:

<P><STRONG>and</STRONG>, <STRONG>array</STRONG>, <STRONG>do</STRONG>,
<STRONG>else</STRONG>, <STRONG>endo</STRONG>, <STRONG>endif</STRONG>,
<STRONG>endproc</STRONG>, <STRONG>endwhile</STRONG>,
<STRONG>if</STRONG>, <STRONG>line</STRONG>, <STRONG>not</STRONG>,
<STRONG>or</STRONG>, <STRONG>proc</STRONG>, <STRONG>read</STRONG>,
<STRONG>readstr</STRONG>, <STRONG>retval</STRONG>,
<STRONG>var</STRONG>, <STRONG>while</STRONG>,
<STRONG>writestr</STRONG>, <STRONG>write</STRONG>.

<P>The symbols used in Paxi are:

<P> <STRONG>+</STRONG>, <STRONG>-</STRONG>, <STRONG>*</STRONG>,
<STRONG>/</STRONG>, <STRONG>=</STRONG>, <STRONG><</STRONG>,
<STRONG><=</STRONG>, <STRONG>>=</STRONG>, <STRONG>></STRONG>,
<STRONG>#</STRONG>, <STRONG>(</STRONG>, <STRONG>)</STRONG>,
<STRONG>[</STRONG>, <STRONG>]</STRONG>, <STRONG>,</STRONG>(comma),
<STRONG>;</STRONG>, <STRONG>&quot;</STRONG>(double quote),
<STRONG>'</STRONG>(single quote), <STRONG>//</STRONG>.

<P>Paxi also has <EM>string literals</EM> (any character string
enclosed in double quote marks), <EM>characters</EM> (any single
character enclosed in single quotes), and <EM>number literals</EM>.
Number literals are (signed) decimal integers.

<P><H3>Paxi Syntax</H3>

<PRE>
1.  &lt;program&gt; -&gt; &lt;globals_list&gt; &lt;procedure_list&gt;

2.  &lt;globals_list&gt; -&gt; &lt;globals_list&gt; &lt;globals_decl&gt; | EMPTY

3.  &lt;globals_decl&gt; -&gt; &lt;global_var_decl&gt; | &lt;array_decl&gt;

4.  &lt;global_var_decl&gt; -&gt; var &lt;global_var_list&gt; ;

5.  &lt;global_var_list&gt; -&gt; &lt;global_var_list&gt; , ID | ID

6.  &lt;array_decl&gt; -&gt; array &lt;array_list&gt; ;

7.  &lt;array_list&gt; -&gt; &lt;array_list&gt; , &lt;single_array&gt; | &lt;single_array&gt;

8.  &lt;single_array&gt; -&gt; NUMBER ID

9.  &lt;procedure_list&gt; -&gt; procedure_list procedure_decl | EMPTY

10.  &lt;procedure_decl&gt; -&gt; proc ID ( &lt;formal_parameters&gt; ) &lt;locals_list&gt;
                        &lt;statement_list&gt; endproc

11. &lt;formal_parameters&gt; -&gt; &lt;formal_list&gt; | EMPTY

12. &lt;formal_list&gt; -&gt; &lt;formal_list&gt; , ID | ID

13. &lt;locals_list&gt; -&gt; &lt;locals_list&gt; &lt;local_decl&gt; | EMPTY

14. &lt;local_decl&gt; -&gt; var &lt;local_var_list&gt; ;

15. &lt;local_var_list&gt; -&gt; &lt;local_var_list&gt; , ID | ID

16. &lt;statement_list&gt; -&gt; &lt;statement_list&gt; &lt;statement&gt; ; | EMPTY

17. &lt;statement&gt; -&gt; &lt;assignment&gt; | &lt;conditional&gt; | &lt;loop&gt; | &lt;io&gt; |
                   &lt;call&gt; | &lt;return_value&gt;

18. &lt;assignment&gt; -&gt; &lt;variable&gt; = &lt;arithmetic_expression&gt;
               
19. &lt;conditional&gt; -&gt; if &lt;boolean_expression&gt; &lt;statement_list&gt;
                     &lt;else_clause&gt; endif
 
20. &lt;else_clause&gt; -&gt; else &lt;statement_list&gt; | EMPTY

21. &lt;loop&gt; -&gt; &lt;while_loop&gt; | &lt;do_loop&gt;

22. &lt;while_loop&gt; -&gt; while &lt;boolean_expression&gt; &lt;statement_list&gt;
                    endwhile

23. &lt;do_loop&gt; -&gt; do &lt;statement_list&gt; endo while &lt;boolean_expression&gt;

24. &lt;io&gt; -&gt; &lt;read_statement&gt; | &lt;write_statement&gt; | &lt;line_statement&gt;

25. &lt;call&gt; -&gt; ID ( &lt;actual_parameters&gt; )

26. &lt;return_value&gt;-&gt; retval &lt;arithmetic_expression&gt;

27. &lt;actual_parameters&gt; -&gt; &lt;parameter_list&gt; | EMPTY

28. &lt;parameter_list&gt; -&gt; &lt;parameter_list&gt; , &lt;arithmetic_expression&gt;
                        | &lt;arithmetic_expression&gt;

29. &lt;quantity&gt; -&gt; &lt;variable&gt; | NUMBER | &lt;call&gt; | ' CHARACTER '

30. &lt;variable&gt; -&gt; ID | ID [ &lt;arithmetic_expression&gt; ]

31. &lt;read_statement&gt; -&gt; read ( &lt;variable&gt; ) | readstr ( ID )

32. &lt;write_statement&gt; -&gt; write ( &lt;arithmetic_expression&gt; )
                         | writestr ( " STRING " ) | writestr ( ID )

33. &lt;line_statement&gt; -&gt; line

34. &lt;arithmetic_expression&gt; -&gt; &lt;arithmetic_expression&gt; &lt;add_operator&gt;
                               &lt;arithmetic_term&gt; | &lt;arithmetic_term&gt;

35. &lt;arithmetic_term&gt; -&gt; &lt;arithmetic_term&gt; &lt;mult_operator&gt;
                         &lt;arithmetic_factor&gt; | &lt;arithmetic_factor&gt;

36. &lt;arithmetic_factor&gt; -&gt; &lt;quantity&gt; | ( &lt;arithmetic_expression&gt; )

37. &lt;add_operator&gt; -&gt; + | -

38. &lt;mult_operator&gt; -&gt; * | /

39. &lt;boolean_expression&gt; -&gt; &lt;boolean_expression&gt; or &lt;boolean_term&gt;
                            | &lt;boolean_term&gt;

40. &lt;boolean_term&gt; -&gt; &lt;boolean_term&gt; and &lt;boolean_factor&gt;
                      | &lt;boolean_factor&gt;

41. &lt;boolean_factor&gt; -&gt; not &lt;boolean_atom&gt; | &lt;boolean_atom&gt;

42. &lt;boolean_atom&gt; -&gt; ( &lt;arithmetic_expression&gt; &lt;relational_operator&gt;
                      &lt;arithmetic_expression&gt; )
                      | ( &lt;boolean_expression&gt; )

43. &lt;relational_operator&gt; -&gt; = | &lt; | &lt;= | &gt; | &gt;= | #
</PRE>


</HTML>
